package combinations77

// Combinations77 returns all combinations of k elements from the input slice.
// 思路：
// 1. 递归：从第一个元素开始，选择或不选择当前元素，递归处理剩余元素。
// 2. 终止条件：当 k 为 0 时，返回当前组合；当 k 大于剩余元素数量时，返回空切片。
// 3. 选择当前元素：将当前元素加入组合，递归处理剩余元素，k 减 1。
// 4. 不选择当前元素：递归处理剩余元素，k 不变。
// 5. 返回组合结果：将选择和不选择当前元素的结果合并。
func Combinations77(nums []int, k int) [][]int {
	// 终止条件
	// 返回 [][]int{{}} 代表当前组合为空；返回空切片代表没有组合
	// 例如：nums = [1,2,3], k = 0
	// 选择0个元素，返回一个包含空切片的切片，代表当前组合为空
	// 例如：nums = [1,2,3], k = 4
	// 选择4个元素，返回一个空切片，代表没有组合
	// 这个返回会影响到遍历，前者会进入循环，后者不会进入循环。
	if k == 0 {
		return [][]int{{}}
	}
	if len(nums) < k {
		return [][]int{}
	}

	result := [][]int{}
	for i := 0; i < len(nums); i++ {
		num := nums[i]
		// 选择当前元素
		// 从剩余的切片中选择 k-1 个元素
		// 递归调用
		// 组合的结果是当前元素加上剩余的组合，可能包含多个，每个组合需要和当前元素num组合成一个新的组合
		// 例如：nums = [1,2,3], k = 2
		// 选择1，剩余的元素是[2,3]，需要从中选择1个元素
		// 组合的结果是[[1,2],[1,3]]
		// 选择2，剩余的元素是[3]，需要从中选择1个元素
		// 组合的结果是[[2,3]]
		// 选择3，剩余的元素是[]，需要从中选择1个元素
		// 组合的结果是[]
		combs := Combinations77(nums[i+1:], k-1)
		for _, comb := range combs {
			cur_result := append([]int{num}, comb...) // 每一个comb都是一个组合，形式是切片形式，和当前元素构成完整的组合
			// 最终组合的结果集中追加上当前结果组合
			result = append(result, cur_result)
		}
	}
	return result
}
